Integer decomposition for polyhedra defined by nearly totally unimodular matrices.

摘要

Abstract. We call a matrix $A$ nearly totally unimodular if it can be obtained from a totally unimodular matrix $\tilde{A}$ by adding to each row of $\tilde{A}$ an integer multiple of some fixed row $a^{\transp}$ of $\tilde{A}$. For an integer vector $b$ and a nearly totally unimodular matrix $A$, we denote by $P_{A,b}$ the integer hull of the set $\{x\in\mathbb{R}^n\mid Ax\leq b\}$. We show that $P_{A,b}$ has the integer decomposition property and that we can find a decomposition of a given integer vector $x\in kP_{A,b}$ in polynomial time. An interesting special case that plays a role in many cyclic scheduling problems is when $A$ is a circular-ones matrix. In this case, we show that given a nonnegative integer $k$ and an integer vector $x$, testing if $x\in kP_{A,b}$ and finding a decomposition of $x$ into $k$ integer vectors in $P_{A,b}$ can be done in time $O(n(n+m)+\text{size}(x))$, where $A$ is an $m\times n$ matrix. We show that the method unifies some known results on coloring circular arc graphs and edge coloring nearly bipartite graphs. It also gives an efficient algorithm for a packet scheduling problem for smart antennas posed by Amaldi, Capone, and Malucelli in [Fourth ALIO/EURO Workshop on Applied Combinatorial Optimization, Pucón, Chile, 2002]; [Proceedings of the Second Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Vol. 1, 2003, pp. 1--4]. Key words. integer decomposition, totally unimodular, circular arc graph, nearly bipartite graph, cyclic scheduling, coloring AMS Subject Classifications. 90C10 , 05C15 , 05C70